/**
 * LeetCode 59. 螺旋矩阵 II
 */
public class Solution_59 {
    /**
     * 模拟
     * <p>
     * 时间复杂度：O(n^2)
     * <p>
     * 空间复杂度：O(1)
     */
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        // 矩阵的上、下、左、右边界索引
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int x = 1, target = n * n;

        while (x <= target) {
            // 从左到右
            for (int i = left; i <= right; i++) {
                ans[top][i] = x;
                x++;
            }
            top++;
            // 从上到下
            for (int i = top; i <= bottom; i++) {
                ans[i][right] = x;
                x++;
            }
            right--;
            // 从右到左
            for (int i = right; i >= left; i--) {
                ans[bottom][i] = x;
                x++;
            }
            bottom--;
            // 从下到上
            for (int i = bottom; i >= top; i--) {
                ans[i][left] = x;
                x++;
            }
            left++;
        }
        return ans;
    }
}
